package LinkList;

import java.util.List;

public class MySingleList implements  IList{
    static  class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public  ListNode head;
    public void createList(){
        ListNode node = new ListNode(12);
        ListNode node1 = new ListNode(23);
        ListNode node2 = new ListNode(34);
        ListNode node3 = new ListNode(45);
        ListNode node4 = new ListNode(56);
        node.next =node1;
        node1.next =node2;
        node2.next =node3;
        node3.next =node4;
        this.head =node;
    }
    @Override
    public void display() {
        while(head!=null){
            System.out.print(head.val+" ");
            head =head.next;
        }
        System.out.println();
    }
    public void display2(ListNode newHead) {
        ListNode cur =newHead;
        while(cur !=null){
            System.out.print(cur.val+" ");
            cur =cur.next;
        }
        System.out.println();
    }
    @Override
    public int size() {
        int len =0;
        ListNode cur =head;
        while(cur !=null){
            len++;
            cur =cur.next;
        }
        return len;
    }
    @Override
    public void addFirst(int data) {
        ListNode node =new ListNode(data);
        node.next =head;
        head =node;
    }

    @Override
    public void addLast(int data) {
        ListNode node =new ListNode(data);
        ListNode cur =head;
        if(cur==null){
            head=node;
            return ;
        }
        while(cur.next !=null){
            cur=cur.next;
        }
        cur.next =node;
    }

    @Override
    public void addIndex(int index, int data) {
        int len =size();
        if(index <0||index> len){
            System.out.println("index位置不合法");
            return;
        }
        //前面插入
        if(index==0){
            addFirst(data);
            return;
        }
        if(index==len){
            addLast(data);
            return;
        }
        //中间插入
        ListNode cur =head;
        while(index-1 !=0){
            cur =cur.next;
            index--;
        }
        ListNode node =new ListNode(data);
        node.next =cur.next;
        cur.next =node;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur =head;
        while(cur !=null){
            if(cur.val==key){
                return true;
            }
            cur =cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head==null){
            return;
        }
        if(head.val==key){
            head =head.next;
            return;
        }
        ListNode cur =findNodeOfKey(key);
        if(cur==null){
            return ;
        }
        ListNode del =cur.next;
        cur.next =del.next;
    }
    private  ListNode findNodeOfKey(int key){
        ListNode cur =head;
        while(cur !=null){
            if(cur.next.val==key){
                return cur;
            }
            cur =cur.next;
        }
        return null;
    }
    @Override
    public void removeAllKey(int key) {
        if(head==null){
            return;
        }
        ListNode cur =head.next;
        ListNode prev =head;
        while(cur !=null){
            if(cur.val==key){
               prev.next=cur.next;
               cur =cur.next;
            }else{
                prev =cur;
                cur=cur.next;
            }
        }
        if(cur.val ==key){
            head =head.next;
        }
    }
    @Override
    public void clear() {
        ListNode cur =head;
        while(cur !=null){
            ListNode curN =cur.next;
            cur.next =null;
            cur =curN;
        }
    }
    public ListNode removeElements(ListNode head, int val) {
        while(head !=null && head.val==val){
            head =head.next;
        }
        if(head==null){
            return head;
        }
        ListNode cur =head;
        while(cur.next !=null){
            if(cur.next.val ==val){
                cur.next =cur.next.next;
            }else{
                cur =cur.next;
            }
        }
        return head;
    }
    //逆转链表
    public ListNode reverseList(ListNode head) {
        if(head==null){
            return  head;
        }
        ListNode cur = head.next;
        head.next = null;
        while(cur !=null){
            ListNode curN =cur.next;
            cur.next =head;
            head =cur;
            cur =curN;
        }
        return head;
    }
    /*给你单链表的头结点 head ，请你找出并返回链表的中间结点。

    如果有两个中间结点，则返回第二个中间结点。*/
    public ListNode middleNode(ListNode head) {
        if(head==null){
            return head;
        }
        ListNode fast =head;
        ListNode slow =head;
        while(fast !=null && fast.next !=null){
            fast =fast.next.next;
            slow =slow.next;
        }
        return slow;
    }
    //找倒数的节点
    public  int KthToLast(ListNode head,int k){
        if(head==null){
            return -1;
        }
        ListNode fast =head;
        ListNode slow =head;
        int count =0;
        while(count !=k-1){
            fast =fast.next;
            if(fast ==null){
                return -1;
            }
            count++;
        }
        while(fast !=null){
            fast =fast.next;
            slow =slow .next;
        }
        return slow.val;
    }
    public ListNode partition(ListNode head, int x) {
        ListNode bs =null;
        ListNode be =null;
        ListNode as =null;
        ListNode ae =null;
        ListNode cur =head;
        while(cur !=null){
            if(cur.val<x){
                //第一次插入
                if(bs==null){
                    bs=be=null;
                }else{
                    be.next =cur;
                    be =be.next;
                }
            }else{
                if(as==null){
                    as=ae=null;
                }else{
                    ae.next =cur;
                    ae=ae.next;
                }
            }
            cur =cur.next;
        }
        if(bs==null){
            return as;
        }
        be.next=be;
        //不管第二部分是否最后一个节点为空，都手动置为空
        if(as!=null){
            be.next=null;
        }
        return  bs;
    }
    //给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
    // 如果两个链表不存在相交节点，返回 null
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode pl =headA;
        ListNode ps = headB;
        //1 求长度
        int lenA =0;
        int lenB =0;
        while(pl !=null){
            lenA++;
            pl =pl.next;
        }
        while(ps !=null){
            lenB++;
            ps =ps.next;
        }
        pl =headA;
        ps =headB;
        //2.求差值
        int len =lenA -lenB;
        if(len <0){
            pl =headB;
            ps =headA;
            len =lenB-lenA;
        }
        //3.让最长的链表 走len步
        while(len !=0){
            pl =pl.next;
            len--;
        }
        //同时操作 pl和ps，直到他们相遇
        while(pl !=ps){
            pl =pl.next;
            ps =ps.next;
        }
        if(pl ==null){
            return  null;
        }
        return pl;
    }
    public boolean hasCycle(ListNode head) {
        ListNode fast =head;
        ListNode slow =head;
        while(fast !=null && fast.next !=null){
            fast =fast.next.next;
            slow =slow.next;
            if(fast == slow){
                return  true;
            }
        }
        return  false;
    }
}
